﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SearchCompare
{
    public class BinarySearchForest
    {
        //Dictionary holds root nodes
        //If a value already exists in the dictionary then add it to the tree
        Dictionary<int, NodeWrapper> _forest;

        public BinarySearchForest()
        {
            _forest = new Dictionary<int, NodeWrapper>();
        }

        /// <summary>
        /// Wraps a node so references can be stored in the dictionary
        /// </summary>
        private unsafe class NodeWrapper
        {
            public Node* address;
            public NodeWrapper(Node* node)
            {
                address = node;
            }
        }
        
        private int GetHash(Node node)
        {
            //tune this to adjust frequency distribution of items in buckets
            int a = 2;

            //mod it to 65536
            ushort hash = (ushort)(a * node._value % (65536));

            //shift it right to fit between 0 and 127
            return hash >> 9;

        }

        /// <summary>
        /// Add a node to the forest. If there is a conflict then add to the tree at that element in the table. Returns true if the add was successful.
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public unsafe bool Add(Node* node)
        {
            //Hash the node
            int hashValue = GetHash(*node);
            
            //See if the hash is already in the table
            if (_forest.ContainsKey(hashValue))
                return TreeUtil.Add(node, ref _forest[hashValue].address);

            else
            {
                //if it is not in the dictionary already then just add it normally
                _forest.Add(hashValue, new NodeWrapper(node));
                return true;
            }
        }

        public unsafe bool AVLAdd(Node* node)
        {
            //Hash the node
            int hashValue = GetHash(*node);

            //See if the hash is already in the table
            if (_forest.ContainsKey(hashValue))
                return TreeUtil.AVLAdd(node, ref _forest[hashValue].address);

            else
            {
                //if it is not in the dictionary already then just add it normally
                _forest.Add(hashValue, new NodeWrapper(node));
                return true;
            }
        }

        /// <summary>
        /// Returns the number of comparisons required to find a node in the forest
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public unsafe int MeasureComparisons(ushort searchValue)
        {
            int hash = GetHash(new Node(searchValue));

            //if the hash table contains the key then return the number of comparisons required to
            //find the node + 1 for the hash comparison
            if (_forest.ContainsKey(hash))
                return TreeUtil.MeasureComparisons(searchValue, _forest[hash].address) + 1;

            //if the forest does not contain the node then return 1 for the hash comparison
            else return 1;
        }
        
        /// <summary>
        /// Returns a node with the specified value 
        /// </summary>
        /// <param name="searchValue"></param>
        /// <returns></returns>
        public unsafe Node* Find(ushort searchValue)
        {
            int hash = GetHash(new Node(searchValue));

            if (_forest.ContainsKey(hash))
                return TreeUtil.FindNode(searchValue, _forest[hash].address);

            else return null;
        }

        /// <summary>
        /// Prints the tree to the screen
        /// </summary>
        public unsafe void Print()
        {
            foreach (KeyValuePair<int, NodeWrapper>root in _forest)
            {
                Console.WriteLine("Key: {0}", root.Key);
                TreeUtil.PrintTree(root.Value.address);
            }
        }

        
        /// <summary>
        /// Prints the number of nodes in a tree to the console
        /// </summary>
        /// <param name="root"></param>
        public unsafe void PrintCounts()
        {
            int tree = 0;
            foreach (KeyValuePair<int,NodeWrapper> root in this._forest)
            {
                Console.WriteLine("Tree {0} size: {1}", tree, TreeUtil.Count(root.Value.address));
                tree++;
            }
        }

        /// <summary>
        /// Print the heights of the trees in the forest
        /// </summary>
        public unsafe void PrintHeights()
        {
            foreach (KeyValuePair<int, NodeWrapper> root in this._forest)
            {
                Console.WriteLine("Tree height: {0}", TreeUtil.AdjustHeight(root.Value.address));
            }

        }

    }
}
